package sort;

public class MergeSort extends Sort {

    public static void main(String[] args) {
        sort = new MergeSort();
        sort.run();
    }

    @Override
    protected void sort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int middle = (start + end) / 2;
        sort(nums, start, middle);
        sort(nums, middle + 1, end);
        merge(nums, start, middle, end);
    }

    private void merge(int[] nums, int start, int middle, int end) {
        int[] tempNums = new int[end - start + 1];
        int left = start;
        int right = middle + 1;
        int tempIndex = 0;
        while (left <= middle && right <= end) {
            if (nums[left] <= nums[right]) {
                tempNums[tempIndex++] = nums[left++];
            } else {
                tempNums[tempIndex++] = nums[right++];
            }
        }

        while (left <= middle) {
            tempNums[tempIndex++] = nums[left++];
        }

        while (right <= end) {
            tempNums[tempIndex++] = nums[right++];
        }

        for (int i = 0; i < tempNums.length; i++) {
            nums[start + i] = tempNums[i];
        }
    }
}
